A network is a group of two or more network-accessible devices linked by wired or wireless connections. A network-accessible device can be a desktop computer, a personal digital assistant, a mobile or laptop computer, a cellular or mobile telephone, etc. A node is a network-accessible device that is connected to a network.
Networks can be divided into two basic types: circuit-switched and packet-switched. In packet-switched networks, large blocks of data are divided into a number of small packets. A packet is a small block of data sent across a network. Typically, each packet contains a source and destination address as well as the small block of data.
Routers are specialized computers that interconnect two networks and pass packets from one to another. Generally, a router examines the destination address of each packet that passes through the router. Based on the destination address, the router decides which path a packet will travel during the next hop in the packet's journey. Routers use route tables to store information about how to reach destinations.
Typically, route tables contain two pieces of information about each destination that a router serves: the address of the destination network and the address of the next router along the path to each destination. The next router along the path to a destination is called the next hop. Routers read a packet's destination address and send the packet to the next hop towards the packet's final destination.
Routing protocols discover paths to destinations and provide that information to the processes that manage route tables. Rediscovery means that a routing protocol discovers a route again after the routing protocol has been inoperative for a period of time. Examples of routing protocols are: open shortest path first (OSPF), routing information protocol (RIP), and border gateway protocol (BGP). Routing protocols are well known in the art and will not be further described except as they relate to the invention that is the subject of this application. For a further discussion of routing protocols see, e.g., Internet Engineering Task Force (IETF) Network Working Group, Request for Comments (RFC) 2328, “OSPF Version 2” April 1998; IETF Networking Group, RFC 1930, “Guidelines for Creation, Selection, and Registration of an Autonomous System (AS),” March 1996; and IETF Network Working Group, RFC 2453 “RIP Version 2,” November 1998.
Peering is a relationship between two or more networks in which the networks agree to forward packets directly to each other. Each routing protocol of a given type (e.g., OSPF, RIP, BGP, etc.) residing on a router in one network forwards packets to a routing protocol of the same type in another network. Routing protocols of the same type (e.g., OSPF, RIP, BGP, etc.) that directly forward packets to each other are called peer routing protocols or simply peers.
Conventional routers employ multiple routing protocols that are compiled as a single executable file. Each routing protocol maintains a separate routing database in a data structure specific to the routing protocol and the router maintains a central route table containing the routes discovered by each routing protocol. For the purposes of this application, the routing database maintained by a routing protocol is a type of route table. Periodically, routing protocols become inoperable for reasons such as the routing protocol is being updated or the routing protocol has suffered a technical malfunction. If all of the routing protocols operating on a router are integrated into a single executable process, the entire router is inoperative if a single routing protocol is inoperative.
A solution to the deficiencies of the conventional router is to separate the routing protocols so that each routing protocol executes as an independent process. If each routing protocol executes independently, then any particular routing protocol can be inoperative without making the entire router inoperative. If the routing protocols are separated, however, they do not automatically share information with each other about the routes they discover. Therefore, it is desirable for the router to maintain a central route table that each routing protocol can interact with independently.
A central route table that operates independently of the routing protocols must include a mechanism for quick and efficient route table updates, particularly when all routes for a given protocol must be purged and quickly relearned. For example, if one of the routing protocols becomes inoperative, then it will not update the entries it has made in the central route table. One or more entries associated with the inoperative protocol may become invalid subsequent to the time the protocol becomes inoperative. Once a routing protocol is determined to be inoperative, a mechanism is needed to quickly purge all of the entries associated with the inoperative routing protocol. Also, a mechanism is needed to transfer a set of entries from a route table that is part of one executing process to a route table that is part of another executing process so that route tables can be quickly populated.